Graph databases support many types of applications such as semantic webs, molecular networks, and social networks. Along with graph analytics, subgraph pattern matching, which finds interesting portions of a large-scale graph, is an essential use of a graph database. Theoretically, subgraph pattern matching is nondeterministic polynomial (NP) complete, which means that it is inherently time-consuming. There are logical heuristics for accelerating graph pattern search, such as pruning unpromising graph portions early. Mechanisms for efficient access of data in memory are a subject of ongoing research.
Subgraph pattern matching entails finding, within a data graph, subgraphs that satisfy a matching semantic against a query graph. Two representative matching semantics are isomorphism and homomorphism. Formally, given a query graph Q(V,E,L) and a data graph G(V′,E′,L′) where V and V′ are vertex sets, E and E′ are edge sets, and L and L′ are labeling functions over vertexes or edges. The labeling function may return a set of labels. Under the isomorphism semantic, solving the subgraph pattern matching is equivalent to finding all mapping functions f:V→V′ that satisfy the following conditions:                1. , L() L′(f())        2. (u,) E, (f(u), f()) E′        3. l (u,) E, L(u,)=L′(f(u),f())        4. if u, then f(u) f()        
Condition 1 says that the data vertex should have at least the label of the query vertex. Conditions 2 and 3 say that if two vertices are connected by an edge in a query graph, then two corresponding vertices in a data graph should be connected by an edge with the same edge label. Condition 4 says that two distinct query vertices cannot be mapped to a single data vertex. Under the homomorphism semantic, only conditions 1-3 are required to qualify as a matching subgraph. As such, the homomorphism semantic can be readily obtained by ignoring condition 4 from the isomorphism semantic. For example, a query graph matches a subgraph (or a mapping function) if the subgraph satisfies the isomorphism matching semantic: f(u1)=v1, f(u2)=v2, and f(u3)=v3.
Graph exploration is executed to find matching subgraphs. Traditionally this involved two primary steps. First, the vertices within a data graph, that satisfy the conditions for the first query vertex of a query graph, are collected. This collection is the root vertex set. Second, the graph exploration is executed by traversing the data graph from the root vertex set. This subtraversal stops if the pattern matching semantic is violated. Traversal can be done in either a breadth-first way, as with PGX.ISO, or a depth-first way, as with TurboISO. However, these particular implementations do not maximize throughput because they do not optimally use memory.